package Offer;

public class T10_1fib {
    int[] memo = new int[101]; //记忆型递归

    public int fib(int n) {
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        if (memo[n] == 0) {
            int ans = (fib(n - 1) + fib(n - 2)) % 1000000007;
            memo[n] = ans;
            return ans;
        }

        return memo[n];
    }
}
